{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Food Buckets to Feed the Hamsters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumBuckets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从房屋收集雨水需要的最少水桶数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>street</code>&nbsp;。<code>street</code>&nbsp;中每个字符要么是表示房屋的&nbsp;<code>'H'</code> ，要么是表示空位的&nbsp;<code>'.'</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以在 <strong>空位</strong>&nbsp;放置水桶，从相邻的房屋收集雨水。位置在 <code>i - 1</code>&nbsp;<strong>或者</strong> <code>i + 1</code>&nbsp;的水桶可以收集位置为 <code>i</code>&nbsp;处房屋的雨水。一个水桶如果相邻两个位置都有房屋，那么它可以收集 <strong>两个</strong> 房屋的雨水。</p>\n",
    "\n",
    "<p>在确保 <strong>每个</strong>&nbsp;房屋旁边都 <strong>至少</strong>&nbsp;有一个水桶的前提下，请你返回需要的 <strong>最少</strong>&nbsp;水桶数。如果无解请返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>street = \"H..H\"\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "我们可以在下标为 1 和 2 处放水桶。\n",
    "\"H..H\" -&gt; \"HBBH\"（'B' 表示放置水桶）。\n",
    "下标为 0 处的房屋右边有水桶，下标为 3 处的房屋左边有水桶。\n",
    "所以每个房屋旁边都至少有一个水桶收集雨水。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>street = \".H.H.\"\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>\n",
    "我们可以在下标为 2 处放置一个水桶。\n",
    "\".H.H.\" -&gt; \".HBH.\"（'B' 表示放置水桶）。\n",
    "下标为 1 处的房屋右边有水桶，下标为 3 处的房屋左边有水桶。\n",
    "所以每个房屋旁边都至少有一个水桶收集雨水。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>street = \".HHH.\"\n",
    "<b>输出：</b>-1\n",
    "<strong>解释：</strong>\n",
    "没有空位可以放置水桶收集下标为 2 处的雨水。\n",
    "所以没有办法收集所有房屋的雨水。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>street = \"H\"\n",
    "<b>输出：</b>-1\n",
    "<strong>解释：</strong>\n",
    "没有空位放置水桶。\n",
    "所以没有办法收集所有房屋的雨水。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>street = \".\"\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "没有房屋需要收集雨水。\n",
    "所以需要 0 个水桶。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= street.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>street[i]</code>&nbsp;要么是&nbsp;<code>'H'</code>&nbsp;，要么是&nbsp;<code>'.'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-food-buckets-to-feed-the-hamsters](https://leetcode.cn/problems/minimum-number-of-food-buckets-to-feed-the-hamsters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-food-buckets-to-feed-the-hamsters](https://leetcode.cn/problems/minimum-number-of-food-buckets-to-feed-the-hamsters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"H..H\"', '\".H.H.\"', '\".HHH.\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        if not hamsters:\n",
    "            return 0\n",
    "        if '.' not in hamsters:\n",
    "            return -1\n",
    "        \n",
    "        n = len(hamsters)\n",
    "        while True:\n",
    "            hamsters = hamsters.replace('H.H', '1')\n",
    "            hamsters = hamsters.replace('.H', '1')\n",
    "            hamsters = hamsters.replace('H.', '1')\n",
    "            break\n",
    "        if 'H' in hamsters:\n",
    "            return -1\n",
    "\n",
    "        return hamsters.count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n = len(hamsters)\n",
    "        st = [0 for _ in range(n)]\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if (i == 0 or i > 0 and hamsters[i - 1] == 'H') and hamsters[i] == 'H' and (i == n - 1 or i + 1 < n and hamsters[i + 1] == 'H'):\n",
    "                return -1\n",
    "            if hamsters[i] == 'H':\n",
    "                if i + 1 < n and hamsters[i + 1] == '.' and (i == 0 or st[i - 1] == 0):\n",
    "                    st[i + 1] = 1\n",
    "                    cnt += 1\n",
    "                elif i > 0 and hamsters[i - 1] == '.' and st[i - 1] == 0:\n",
    "                    st[i - 1] = 1\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        n = len(street)\n",
    "        i = ans = 0\n",
    "        while i < n:\n",
    "            if street[i] == \"H\":\n",
    "                if i + 1 < n and street[i + 1] == \".\":\n",
    "                    ans += 1\n",
    "                    # 直接跳过后续的两个位置\n",
    "                    i += 2\n",
    "                elif i - 1 >= 0 and street[i - 1] == \".\":\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, s: str) -> int:\n",
    "        if s[:2] == 'HH' or s[-2:] == 'HH' or 'HHH' in s or s == 'H':\n",
    "            return -1\n",
    "        s2 = s.replace('H.H', '')\n",
    "        return (len(s) - len(s2)) // 3 + s2.count('H')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, s: str) -> int:\n",
    "        if s[:2] == 'HH' or s[-2:] == 'HH' or 'HHH' in s or s == 'H':\n",
    "            return -1\n",
    "        s2 = s.replace('H.H', '')\n",
    "        return (len(s) - len(s2)) // 3 + s2.count('H')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, s: str) -> int:\n",
    "        if s[:2] == 'HH' or s[-2:] == 'HH' or 'HHH' in s or s == 'H':\n",
    "            return -1\n",
    "        s2 = s.replace('H.H', '')\n",
    "        return (len(s) - len(s2)) // 3 + s2.count('H')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        n = len(street)\n",
    "        i = ans = 0\n",
    "        while i < n:\n",
    "            if street[i] == \"H\":\n",
    "                if i + 1 < n and street[i + 1] == \".\":\n",
    "                    ans += 1\n",
    "                    # 直接跳过后续的两个位置\n",
    "                    i += 2\n",
    "                elif i - 1 >= 0 and street[i - 1] == \".\":\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n = len(hamsters)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            if hamsters[i] == '.':\n",
    "                i += 1\n",
    "            else:\n",
    "                if i + 1 < n and hamsters[i+1] == '.':\n",
    "                    res += 1\n",
    "                    i += 3\n",
    "                elif i - 1 >= 0 and hamsters[i-1] == '.':\n",
    "                    res += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n = len(hamsters)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if hamsters[i] == 'H':\n",
    "                # print(i)\n",
    "                if i + 1 < n and hamsters[i+1] == '.':\n",
    "                    # print(i)\n",
    "                    res += 1\n",
    "                    i += 2\n",
    "                elif i - 1 >= 0 and hamsters[i-1] == '.':\n",
    "                    res += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n=len(hamsters)\n",
    "        i=0\n",
    "        ans=0\n",
    "        while i<n:\n",
    "            if hamsters[i]=='H':\n",
    "                if i+1<n and hamsters[i+1]=='.':\n",
    "                    ans+=1\n",
    "                    i+=2\n",
    "                elif i-1>=0 and hamsters[i-1]=='.':\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    return -1\n",
    "            i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n , ans, i = len(hamsters), 0, 0\n",
    "        while i < n:\n",
    "            if hamsters[i] == '.':\n",
    "                i += 1\n",
    "                continue\n",
    "            if i < n - 1 and hamsters[i + 1] == '.':\n",
    "                ans += 1\n",
    "                i += 2\n",
    "            elif i > 0 and hamsters[i - 1] == '.':\n",
    "                ans += 1\n",
    "            else:\n",
    "                return -1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        i=0\n",
    "        n=len(hamsters)\n",
    "        ans=0\n",
    "        while i<n:\n",
    "            if hamsters[i]==\"H\":\n",
    "                if i+1<n and hamsters[i+1]=='.':\n",
    "                    ans+=1\n",
    "                    i+=2\n",
    "                elif i-1>=0 and hamsters[i-1]==\".\":\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    return -1\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n=len(hamsters)\n",
    "        i=0\n",
    "        ans=0\n",
    "        while i<n:\n",
    "            if hamsters[i]=='H':\n",
    "                if i+1<n and hamsters[i+1]=='.':\n",
    "                    ans+=1\n",
    "                    i+=2\n",
    "                elif i-1>=0 and hamsters[i-1]=='.':\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    return -1\n",
    "            i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        lastpos = -2\n",
    "        ans = 0\n",
    "        n = len(hamsters)\n",
    "        for i,ch in enumerate(hamsters):\n",
    "            if ch =='H':\n",
    "                if lastpos == i-1:\n",
    "                    continue\n",
    "                elif i+1<n and hamsters[i+1]=='.':\n",
    "                    lastpos = i+1\n",
    "                    ans+=1\n",
    "                elif i>0 and hamsters[i-1]=='.':\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    return -1\n",
    "        return ans \n",
    "                      \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\r\n",
    "        ans = 0\r\n",
    "        n = len(hamsters)\r\n",
    "        i = 0\r\n",
    "        while i < n:\r\n",
    "            #如果是房屋，那么需要放水桶\r\n",
    "            if hamsters[i] == 'H':\r\n",
    "                #优先放到房屋右侧\r\n",
    "                if i < n - 1 and hamsters[i+1] == '.':\r\n",
    "                    ans += 1\r\n",
    "                    i += 2\r\n",
    "                #如果房屋右侧已经有水桶，那么放到房屋左侧\r\n",
    "                elif i >= 1 and hamsters[i-1] == '.':\r\n",
    "                    ans += 1\r\n",
    "                #如果房屋两侧都不能放水桶，那么无解\r\n",
    "                else:\r\n",
    "                    return -1\r\n",
    "            i += 1\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        n = len(street)\n",
    "        street = list(street)\n",
    "        ans = 0\n",
    "        cnt = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "        \tif street[i] == '.':\n",
    "        \t\tif i > 0 and street[i-1] == 'H':\n",
    "        \t\t\tcnt[i-1] += 1\n",
    "        \t\t\tstreet[i] = 'B'\n",
    "        \t\tif i + 1 < n and street[i+1] == 'H':\n",
    "        \t\t\tcnt[i+1] += 1\n",
    "        \t\t\tstreet[i] = 'B'\n",
    "        for i in range(n):\n",
    "        \tif street[i] == 'H' and cnt[i] == 0:\n",
    "        \t\treturn -1\n",
    "        \tif street[i] == 'B':\n",
    "        \t\tif (i > 0 and cnt[i-1] == 1) or (i + 1 < n and cnt[i+1] == 1):\n",
    "        \t\t\tans += 1\n",
    "        \t\telse:\n",
    "        \t\t\tif i > 0:\n",
    "        \t\t\t\tcnt[i-1] -= 1\n",
    "        \t\t\tif i + 1 < n:\n",
    "        \t\t\t\tcnt[i+1] -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(street)\n",
    "        if n == 1:\n",
    "            return -1 if street == 'H' else 0\n",
    "        for i in range(n):\n",
    "            if i==0 and street[i] == 'H':\n",
    "                if street[1] ==\".\":\n",
    "                    ans = ans+1\n",
    "                    street = street[0]+'B'+street[2:]\n",
    "                else:\n",
    "                    return -1\n",
    "            if i == n-1 and street[i] == \"H\":\n",
    "                if street[i-1] == \".\":\n",
    "                    ans = ans+1\n",
    "                    return ans\n",
    "                elif street[i-1] == \"B\":\n",
    "                    return ans\n",
    "                else:\n",
    "                    return -1\n",
    "            if 0<i<n-1 and street[i] == 'H':\n",
    "                if street[i-1] == \"B\":\n",
    "                    continue\n",
    "                elif street[i+1] == \".\":\n",
    "                    street = street[:i+1]+'B'+street[i+2:]\n",
    "                    ans +=1\n",
    "                elif street[i-1] == \".\":\n",
    "                    ans +=1\n",
    "                else: return -1\n",
    "            \n",
    "        return ans \n",
    "                \n",
    "        \"\"\"\n",
    "        #直接计数\n",
    "        n = len(street)\n",
    "        if n == 1:\n",
    "            return -1 if street == 'H' else 0\n",
    "        if street[:2] =='HH' or street[-2:] == 'HH':\n",
    "            return -1\n",
    "        ans = street.count('H')\n",
    "        if n== 2:\n",
    "            return ans\n",
    "        i = 0\n",
    "        while i <n-2:\n",
    "            s = street[i:i+3]\n",
    "            if s == 'HHH':\n",
    "                return -1\n",
    "            if s == 'H.H':\n",
    "                ans -= 1\n",
    "                if i+3<n and street[i+3] ==\".\":\n",
    "                    i = i+3\n",
    "                    continue\n",
    "            i = i+1\n",
    "        return ans\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        n=len(street)\n",
    "        street=list(street)\n",
    "        is_covered=[0]*n\n",
    "        res=0\n",
    "        for i,c in enumerate(street):\n",
    "            if n-1>i>0 and street[i]=='.'and street[i-1]=='H' and street[i+1]=='H':\n",
    "                if not is_covered[i-1] and not is_covered[i+1]:\n",
    "                    street[i]='B'\n",
    "                    is_covered[i-1]=1\n",
    "                    is_covered[i+1]=1\n",
    "                    res+=1\n",
    "        for i,c in enumerate(street):\n",
    "            if c=='H' and not is_covered[i]:\n",
    "                if (i-1>=0 and street[i-1]=='.') or (i+1<n and street[i+1]=='.'):\n",
    "                    res+=1\n",
    "                else:\n",
    "                    return -1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        l, res = len(hamsters), 0\n",
    "        hamsters = list(hamsters)\n",
    "\n",
    "        for i in range(1, l-1):\n",
    "            if hamsters[i] == '.' and hamsters[i-1] == hamsters[i+1] == 'H':\n",
    "                res += 1\n",
    "                hamsters[i-1] = hamsters[i+1] = 'O'\n",
    "        \n",
    "        def get_buckets(house):\n",
    "            r = 0\n",
    "            for i in range(l):\n",
    "                if house[i] == 'H':\n",
    "                    if i and house[i-1] == '.':\n",
    "                        r += 1\n",
    "                        house[i] = 'O'\n",
    "                    elif i + 1 < l and house[i+1] == '.':\n",
    "                        r += 1\n",
    "                        house[i] = 'O'\n",
    "\n",
    "            if any(v == 'H' for v in house):\n",
    "                r = -1\n",
    "            return r\n",
    "            \n",
    "\n",
    "        r = get_buckets(hamsters[::])\n",
    "        l = get_buckets(hamsters[::-1])\n",
    "        # print(r,l)\n",
    "\n",
    "        if -1 in [r, l]:\n",
    "            return -1\n",
    "        if r and l:\n",
    "            return res + min(r, l)\n",
    "       \n",
    "        return res + r or l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n = len(hamsters)\n",
    "        hamsters = 'H' + hamsters + 'H'\n",
    "        f = [0] * (n + 1)\n",
    "        s = list(hamsters)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i] == 'H':\n",
    "                if s[i - 1] == 'B': continue\n",
    "                elif s[i + 1] == '.':\n",
    "                    s[i + 1] = 'B'\n",
    "                    ans += 1\n",
    "                elif s[i - 1] == '.':\n",
    "                    ans += 1\n",
    "                else: return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        temp = []\n",
    "        if len(street) == 1:\n",
    "            if street[0] == 'H':\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "        for i in range(len(street)):\n",
    "            if street[i] == 'H':\n",
    "                if i+1 < len(street) and street[i+1] == 'H' and i+2 < len(street) and street[i+2] == 'H':\n",
    "                    return -1\n",
    "                temp.append(i)\n",
    "        if street[0] == 'H' and len(street) > 1:\n",
    "            if street[1] == 'H':\n",
    "                return -1\n",
    "        if street[-1] == 'H' and len(street) > 1:\n",
    "            if street[-2] == 'H':\n",
    "                return -1\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < len(temp):\n",
    "            if i + 1 < len(temp):\n",
    "                if temp[i] + 2 == temp[i+1]:\n",
    "                    res += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    res += 1\n",
    "                    i += 1\n",
    "            else:\n",
    "                res += 1\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        hamsters = \"H\" + hamsters + \"H\"\n",
    "        if \"HHH\" in hamsters: return -1\n",
    "        hamsters, lenh, cnt = list(hamsters), len(hamsters), 0\n",
    "        for i in range(1, lenh - 1):\n",
    "            if hamsters[i] == 'H':\n",
    "                if hamsters[i - 1] == 'B': continue\n",
    "                elif hamsters[i - 1] == '.' and hamsters[i + 1] == 'H': cnt += 1\n",
    "                elif hamsters[i + 1] == '.': \n",
    "                    hamsters[i + 1] = 'B'  \n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        hamsters = \"H\" + hamsters + \"H\"\n",
    "        if \"HHH\" in hamsters: return -1\n",
    "        hamsters, lenh, cnt = list(hamsters), len(hamsters), 0\n",
    "        for i in range(1, lenh - 1):\n",
    "            if hamsters[i] == 'H':\n",
    "                if hamsters[i - 1] == 'B': continue\n",
    "                elif hamsters[i - 1] == '.' and hamsters[i + 1] == 'H': cnt += 1\n",
    "                elif hamsters[i + 1] == '.': \n",
    "                    hamsters[i + 1] = 'B'  \n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        if len(hamsters)==1:\n",
    "            if hamsters[0]=='H':\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "        record = list(hamsters)\n",
    "        res = 0\n",
    "        for i in range(len(record)):\n",
    "            if record[i]=='H':\n",
    "                if i==0:\n",
    "                    if record[i+1]=='.':\n",
    "                        record[i+1]='X'\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        return -1\n",
    "                elif i>0 and i<len(record)-1:\n",
    "                    if record[i-1]=='X':\n",
    "                        continue\n",
    "                    elif record[i+1]=='.':\n",
    "                        record[i+1]='X'\n",
    "                        res += 1\n",
    "                    elif record[i-1]=='.':\n",
    "                        record[i-1]='.'\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        return -1\n",
    "                else:\n",
    "                    if record[i-1]=='X':\n",
    "                        continue\n",
    "                    elif record[i-1]=='.':\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        return -1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        # 无法实现的情况：两侧都是房子\n",
    "        n = len(hamsters)\n",
    "        for i, c in enumerate(hamsters):\n",
    "            cnt = 0\n",
    "            if c == 'H' and (i - 1 < 0 or hamsters[i-1] == 'H'):\n",
    "                cnt += 1\n",
    "            if c == 'H' and (i + 1 >= n or hamsters[i+1] == 'H'):\n",
    "                cnt += 1\n",
    "            if cnt == 2:\n",
    "                return -1\n",
    "        \n",
    "        # 贪心，只要左右都有房子就放一下\n",
    "        ans = 0\n",
    "        hamsters = list(hamsters)\n",
    "        for i, c in enumerate(hamsters):\n",
    "            if i-1>=0 and i+1 < n and c == '.' and hamsters[i-1] == 'H' and hamsters[i+1] == 'H':\n",
    "                ans += 1\n",
    "                hamsters[i-1] =  hamsters[i+1] = '.'\n",
    "        \n",
    "        return ans + hamsters.count('H')\n",
    "                \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n = len(hamsters)\n",
    "        aval = [0] * n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if hamsters[i] == 'H':\n",
    "                if aval[i]:continue\n",
    "                if i < n-1 and hamsters[i+1] == 'H' or i == n-1:\n",
    "                    if i >= 1 and hamsters[i-1] == 'H' or i == 0:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        res += 1\n",
    "                elif i < n-1 and hamsters[i+1] == '.':\n",
    "                    aval[i+1] = 1\n",
    "                    if i+2 < n:aval[i+2] = 1\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, s: str) -> int:\n",
    "        s = 'x' + s + 'x'\n",
    "        s = list(s)\n",
    "        ans = 0\n",
    "        for i in range(1, len(s) - 1):\n",
    "            if s[i] == 'H':\n",
    "                if s[i-1] == 'B' or s[i+1] == 'B':\n",
    "                    continue\n",
    "                if s[i+1] == '.':\n",
    "                    s[i+1] = 'B'\n",
    "                    ans += 1\n",
    "                    continue\n",
    "                if s[i-1] == '.':\n",
    "                    s[i-1] = 'B'\n",
    "                    ans += 1\n",
    "                    continue\n",
    "                return -1\n",
    "        return ans\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        ham = list(hamsters)\n",
    "        hamlen = len(ham)\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < hamlen:\n",
    "            if ham[i] != 'H':\n",
    "                i += 1\n",
    "                continue\n",
    "            # 遇到 house 时候\n",
    "            if i-1 >= 0 and ham[i-1] == 'B':\n",
    "                i += 1\n",
    "            elif i +1 < hamlen and ham[i+1] == '.':\n",
    "                ham[i+1] = 'B'\n",
    "                count += 1\n",
    "                i += 2\n",
    "            elif i-1>= 0 and ham[i-1] == '.':\n",
    "                ham[i-1] = 'B'\n",
    "                i += 1\n",
    "                count += 1     \n",
    "            else:\n",
    "                return -1\n",
    "            \n",
    "        return  count\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n = len(hamsters)\n",
    "        if n == 1:\n",
    "            return 0 if hamsters[0] == '.' else -1\n",
    "        if hamsters[0] == 'H' and hamsters[1] == 'H':\n",
    "            return -1\n",
    "        ans = 0\n",
    "        h = [x for x in hamsters]\n",
    "        for i in range(n):\n",
    "            if h[i] == 'H':\n",
    "                if i > 0 and h[i-1] == '#':\n",
    "                    continue\n",
    "                if i + 1 < n and h[i+1] == '.':\n",
    "                    ans += 1\n",
    "                    h[i+1] = '#'\n",
    "                elif i > 0 and h[i-1] == '.':\n",
    "                        ans += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        return ans\n",
    "                \n",
    "                    \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        res = 0\n",
    "        h_list = list(hamsters)\n",
    "        for i in range(1,len(h_list)-1):\n",
    "            if h_list[i]=='.' and h_list[i-1]=='H' and h_list[i+1]=='H':\n",
    "                res+=1\n",
    "                h_list[i-1]='1'\n",
    "                h_list[i+1]='1'\n",
    "                h_list[i]='1'\n",
    "        for i in range(len(h_list)):\n",
    "            if h_list[i]=='H':\n",
    "                if i>0 and h_list[i-1]=='.':\n",
    "                    res+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    if i<len(h_list)-1 and hamsters[i+1]=='.':\n",
    "                        res+=1\n",
    "                    else:\n",
    "                        return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        i = 0\n",
    "        ret = 0\n",
    "        # if hamsters[0]=='H':\n",
    "        #     if hamsters[1%len(hamsters)]=='H':\n",
    "        #         return -1\n",
    "        # if hamsters[-1]=='H':\n",
    "        #     if hamsters[-2]=='H':\n",
    "        #         return -1\n",
    "        mak_list = [False]*len(hamsters)\n",
    "        while i < len(hamsters):\n",
    "            if hamsters[i] == 'H':\n",
    "                if hamsters[max(i-1,0)]=='H' and hamsters[min(i+1,len(hamsters)-1)]=='H':\n",
    "                    return -1\n",
    "                \n",
    "                if not mak_list[i-1]:\n",
    "                    ret +=1\n",
    "                    if hamsters[min(i+1,len(hamsters)-1)] != 'H':\n",
    "                        mak_list[min(i+1,len(hamsters)-1)] = True\n",
    "                    else:\n",
    "                        pass\n",
    "                # else:\n",
    "                #     i= i+1\n",
    "            i = i+1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        chars=list(hamsters)\n",
    "        count=0\n",
    "        # 先求只有一边能放桶的\n",
    "        for i in range(0,len(hamsters)):\n",
    "            if chars[i]=='H':\n",
    "                # 判断前一个\n",
    "                front=(i==0 or chars[i-1]=='H')\n",
    "                # 判断后一个\n",
    "                back=(i==len(chars)-1 or chars[i+1]=='H')\n",
    "                if front and back:\n",
    "                    return -1\n",
    "                elif front and not back:\n",
    "                    chars[i+1]='B'\n",
    "                    count+=1\n",
    "                elif not front and back:\n",
    "                    if chars[i-1]!='B':\n",
    "                        chars[i-1]='B'\n",
    "                        count+=1\n",
    "        for i in range(1,len(chars)-1):\n",
    "            if chars[i]=='H' and chars[i-1]!='B' and chars[i+1]!='B':\n",
    "                chars[i+1]='B'\n",
    "                count+=1\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        hamsters = list(hamsters)\n",
    "        for i in range(len(hamsters)):\n",
    "            if hamsters[i] == 'H':\n",
    "                if i > 0 and hamsters[i - 1] == 'B':\n",
    "                    continue\n",
    "                if i + 1 < len(hamsters) and hamsters[i + 1] == '.':\n",
    "                    hamsters[i + 1] = 'B'\n",
    "                elif i > 0 and hamsters[i - 1] == '.':\n",
    "                    hamsters[i - 1] = 'B'\n",
    "                else:\n",
    "                    return -1\n",
    "        return hamsters.count('B')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        ret = 0\n",
    "        hs = list(hamsters)\n",
    "        cnt = collections.Counter(hamsters)\n",
    "        for i in range(len(hs)):\n",
    "            if hs[i] == \".\" and i > 0 and hs[i - 1] == \"H\":\n",
    "                hs[i - 1] = \"#\"\n",
    "                if i < len(hs) - 1 and hs[i + 1] == \"H\": hs[i + 1] = \"#\"\n",
    "                ret += 1\n",
    "        for i in reversed(range(len(hs))):\n",
    "            if hs[i] == \".\" and i < len(hs) - 1 and hs[i + 1] == \"H\":\n",
    "                if i > 0 and hs[i-1] ==\"H\": hs[i - 1] = \"#\"\n",
    "                hs[i + 1] = \"#\"\n",
    "                ret += 1\n",
    "        cnt = collections.Counter(hs)\n",
    "        return ret if cnt[\"H\"] == 0 else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "\n",
    "        if hamsters == \"H\":\n",
    "            return -1\n",
    "\n",
    "        if hamsters[:2] == \"HH\":\n",
    "            return -1\n",
    "\n",
    "        if hamsters[-2:] == \"HH\":\n",
    "            return -1\n",
    "\n",
    "        if \"HHH\" in hamsters:\n",
    "            return -1\n",
    "\n",
    "        ans = 0\n",
    "        for v in hamsters:\n",
    "            if v == \"H\":\n",
    "                ans += 1\n",
    "        \n",
    "        if ans == 0:\n",
    "            return 0\n",
    "        \n",
    "        record = list(hamsters[:2])\n",
    "        for v in hamsters[2:]:\n",
    "            record.append(v)\n",
    "            if len(record) < 3:\n",
    "                continue\n",
    "                \n",
    "            if \"\".join(record[-3:])==\"H.H\":\n",
    "                # print(record)\n",
    "                ans -= 1\n",
    "                record = []\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        if len(street) == 1:\n",
    "            return 0 if street[0] == \".\" else -1\n",
    "        index = []\n",
    "        num = 0\n",
    "        for i, x in enumerate(street):\n",
    "            if x == \"H\":\n",
    "                num += 1  # 直接记下房子的数量\n",
    "                flag = 1  # 判断是否有房子前后都不空，即无解\n",
    "\n",
    "                # 首元素特殊情况\n",
    "                if i == 0:\n",
    "                    if street[1] == \".\":\n",
    "                        index.append(1)\n",
    "                    else:\n",
    "                        return -1\n",
    "                # 尾元素特殊情况\n",
    "                elif i == len(street) - 1:\n",
    "                    if street[i - 1] == \".\":\n",
    "                        if index and i-1 == index[-1]:\n",
    "                            num-=1\n",
    "                    else:\n",
    "                        return -1\n",
    "\n",
    "                else:\n",
    "                    if street[i - 1] == \".\":\n",
    "                        flag = 0\n",
    "                        if index and i - 1 == index[-1]:  # 可与前一个共用\n",
    "                            num -= 1\n",
    "                            continue\n",
    "                        else:\n",
    "                            index.append(i - 1)\n",
    "                    if street[i + 1] == \".\":\n",
    "                        flag = 0\n",
    "                        index.append(i + 1)\n",
    "\n",
    "                    if flag:\n",
    "                        return -1\n",
    "        return num\n",
    "# print(Solution.minimumBuckets(Solution,\".HH.H\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        stack = []\n",
    "        if street == 'H': return -1\n",
    "        if street[0]  == 'H' and street[1]  == 'H': return -1\n",
    "        if street[-1] == 'H' and street[-2] == 'H': return -1\n",
    "        res = 0\n",
    "        for idx,val in enumerate(street):\n",
    "            if val == 'H':\n",
    "                stack.append(idx)\n",
    "                if len(stack) > 2 and stack[-1]-stack[-3] == 2:\n",
    "                    return -1\n",
    "        while stack:\n",
    "            if len(stack) > 1 and stack[-1] - stack[-2] == 2:\n",
    "                stack.pop()\n",
    "            stack.pop()\n",
    "            res += 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        count = 0\n",
    "        temp = ['H'] + list(street) + ['H']\n",
    "        for i in range(1,len(street)+1):\n",
    "            if temp[i] == 'H':\n",
    "                if temp[i+1] == 'B' or temp[i-1] == 'B':\n",
    "                    continue\n",
    "                if temp[i+1] == '.':\n",
    "                    count += 1\n",
    "                    temp[i+1] = 'B'\n",
    "                elif temp[i-1] == '.':\n",
    "                    count += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        if street == 'H': return -1\n",
    "        if street[0]  == 'H' and street[1]  == 'H': return -1\n",
    "        if street[-1] == 'H' and street[-2] == 'H': return -1\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for idx,val in enumerate(street):\n",
    "            if val == 'H':\n",
    "                stack.append(idx)\n",
    "                if len(stack) > 2 and stack[-1]-stack[-3] == 2:\n",
    "                    return -1\n",
    "        n,cur = len(stack),0\n",
    "        while cur < n:\n",
    "            if cur+1 < n and stack[cur]+2 == stack[cur+1]:\n",
    "                cur += 2\n",
    "            else:\n",
    "                cur += 1\n",
    "            res += 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        if len(street) >= 2:\n",
    "            if street[-1] == 'H' and street[-2] == 'H' or street[0] == 'H' and street[1] == 'H':\n",
    "                return -1\n",
    "        if len(street) == 1 and street[0] == 'H':\n",
    "            return -1\n",
    "        ##如果存在三个连续的就不存在\n",
    "        pos = []\n",
    "        count = 0\n",
    "        for i,ch in enumerate(street):\n",
    "            if ch == 'H':\n",
    "                pos.append(i)\n",
    "                count += 1\n",
    "                if count == 3:\n",
    "                    return -1\n",
    "            else:\n",
    "                count = 0\n",
    "        \n",
    "        count = 0\n",
    "        index = 0\n",
    "        length = len(pos)\n",
    "        while index < length:\n",
    "            if index + 1 < length:\n",
    "                if pos[index] + 2 == pos[index + 1]:\n",
    "                    count += 1\n",
    "                    index += 1\n",
    "                else:\n",
    "                    count += 1\n",
    "            else:\n",
    "                count += 1\n",
    "            index += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        n = len(street)\n",
    "        if (n == 1 and street[0] == '.') or 'H' not in street:\n",
    "            return 0\n",
    "        if (n == 1 and street[0] == 'H') or '.' not in street:\n",
    "            return -1\n",
    "        res = 0\n",
    "        temp = []\n",
    "        for i in range(n):\n",
    "            if street[i] == 'H':\n",
    "                temp.append(i)\n",
    "        i = 0\n",
    "        while i < len(temp):\n",
    "            if i + 1 < len(temp):\n",
    "                if temp[i+1] - temp[i] == 1:\n",
    "                    if temp[i] == 0:\n",
    "                        return -1\n",
    "                    if len(temp) > 2 and ((i + 2 < len(temp) and temp[i+2] - temp[i+1] == 1) or temp[i] - temp[i-1] == 1):\n",
    "                        return -1\n",
    "                if temp[i+1] - temp[i] == 2:\n",
    "                    i += 1\n",
    "            else:\n",
    "                if temp[i] - temp[i-1] == 1 and temp[i] == n - 1:\n",
    "                        return -1\n",
    "            res += 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        n = len(hamsters)\n",
    "        # dp = [0 for i in range(n)]\n",
    "        isB= [0 for i in range(n)]\n",
    "        isF=[0 for i in range(n)]\n",
    "        if n==1:\n",
    "            if hamsters[0]=='H':\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "        for i in range(1, n-1):\n",
    "            if hamsters[i]=='.':\n",
    "                if hamsters[i-1]=='H' and hamsters[i+1]=='H' and isF[i-1]==0 and isF[i+1]==0:\n",
    "                    isB[i]=1\n",
    "                    isF[i-1]=1\n",
    "                    isF[i+1]=1\n",
    "        \n",
    "        for i in range(0, n):\n",
    "            if hamsters[i]=='H' and isF[i]==0:\n",
    "                if i==0:\n",
    "                    if hamsters[i+1]=='H':\n",
    "                        return -1\n",
    "                    else:\n",
    "                        isB[i+1]=1\n",
    "                        isF[i]=1\n",
    "                    continue\n",
    "                if i ==n-1:\n",
    "                    if hamsters[i-1]=='H':\n",
    "                        return -1\n",
    "                    else:\n",
    "                        isB[i-1]=1\n",
    "                        isF[i]=1\n",
    "                    continue\n",
    "                if hamsters[i-1]=='.':\n",
    "                    isB[i-1]=1\n",
    "                    isF[i]=1\n",
    "                else:\n",
    "                    if isF[i-1]==0:\n",
    "                        return -1\n",
    "                    if hamsters[i+1]=='H':\n",
    "                        return -1\n",
    "                    if hamsters[i+1]=='.':\n",
    "                        isB[i+1]=1\n",
    "                        isF[i]=1\n",
    "        return sum(isB)\n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\r\n",
    "        n = len(hamsters)\r\n",
    "        if n == 1:\r\n",
    "            if hamsters[0] == 'H':\r\n",
    "                return -1\r\n",
    "            else:\r\n",
    "                return 0\r\n",
    "        ans = 0\r\n",
    "        used = [0] * n\r\n",
    "        for i in range(0, n - 1):\r\n",
    "            if i == 0:\r\n",
    "                if hamsters[0] == 'H':\r\n",
    "                    if 1 < n and hamsters[1] == '.':\r\n",
    "                        used[1] = 1\r\n",
    "                        ans += 1\r\n",
    "\r\n",
    "                    else:\r\n",
    "                        return -1\r\n",
    "                continue\r\n",
    "            if hamsters[i] == 'H':\r\n",
    "                if used[i - 1] == 1:\r\n",
    "                    continue\r\n",
    "                if hamsters[i + 1] == '.':\r\n",
    "                    used[i + 1] = 1\r\n",
    "                    ans += 1\r\n",
    "                else:\r\n",
    "                    if hamsters[i - 1] == '.':\r\n",
    "                        used[i - 1] = 1\r\n",
    "                        ans += 1\r\n",
    "                    else:\r\n",
    "                        return -1\r\n",
    "\r\n",
    "        # 特殊处理最后一个情况\r\n",
    "        if hamsters[n - 1] == 'H':\r\n",
    "            if hamsters[n - 2] == 'H':\r\n",
    "                return -1\r\n",
    "            elif used[n - 2] == 0:\r\n",
    "                used[n - 2 ] == 1\r\n",
    "                ans += 1\r\n",
    "        print(hamsters, used)\r\n",
    "\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, street: str) -> int:\n",
    "        flag = 0\n",
    "        count = 0\n",
    "        first_street = [street[i] for i in range(len(street))]\n",
    "        second_street = [street[i] for i in range(len(street))]\n",
    "        rank = [0] * len(street)\n",
    "        for i in range(len(street)):\n",
    "            if street[i] == 'H':\n",
    "                if i < len(street) -1:\n",
    "                    if first_street[i+1] == '.':\n",
    "                        first_street[i] = 'A'\n",
    "                        rank[i+1] += 1\n",
    "                if i > 0:\n",
    "                    if first_street[i-1] == '.':\n",
    "                        first_street[i] = 'A'\n",
    "                        rank[i-1] += 1\n",
    "                if street[i] == '.':\n",
    "                    count += 1\n",
    "        if 'H' in first_street:\n",
    "            return -1\n",
    "        for i in range(len(rank)):\n",
    "            if rank[i] == 2:\n",
    "                rank = self.de_rank(i-2, rank)\n",
    "                rank = self.de_rank(i+2, rank)\n",
    "                second_street[i-1] = 'C'\n",
    "                second_street[i+1] = 'C'\n",
    "                rank[i] =0\n",
    "                count += 1\n",
    "        for i in range(len(rank)):\n",
    "            if rank[i] == 1:\n",
    "                rank, second_street = self.de_rank_1(i-1, rank, second_street)\n",
    "                rank, second_street = self.de_rank_1(i+1, rank, second_street)\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "    def de_rank(self, i, rank):\n",
    "        if i < 0 or i >= len(rank):\n",
    "            return rank\n",
    "        if rank[i] != 0:\n",
    "            rank[i] -= 1\n",
    "        return rank\n",
    "    \n",
    "    def de_rank_1(self, i, rank, second_street):\n",
    "        if i >= 0 and i < len(second_street):\n",
    "            if second_street[i] == 'H':\n",
    "                rank = self.de_rank(i+1, rank)\n",
    "                if (i+1)<len(second_street):\n",
    "                    second_street[i+1] = 'C'\n",
    "                rank = self.de_rank(i-1, rank)\n",
    "                if i-1 >= 0:\n",
    "                    second_street[i-1] = 'C'\n",
    "        return rank, second_street"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        count = 0\n",
    "        hamsters = list(hamsters)\n",
    "        for i in range(len(hamsters)):\n",
    "            if hamsters[i]==\"H\":\n",
    "                if 0<=i-1<len(hamsters) :\n",
    "                    if hamsters[i-1]==\"B\":\n",
    "                        print(i,hamsters[i],\"第一种情况i-1在范围内是桶\")\n",
    "                        continue\n",
    "                    elif hamsters[i-1]==\".\":\n",
    "                        print(i,hamsters[i],\"第2种情况i-1在范围内是.\")\n",
    "                        if not 0<=i+1<len(hamsters) or hamsters[i+1]==\"H\":\n",
    "                            hamsters[i-1]=\"B\"\n",
    "                            count += 1\n",
    "                            print(hamsters[i-1],count)\n",
    "                            continue\n",
    "                        else:\n",
    "                            hamsters[i+1]=\"B\"\n",
    "                            count += 1\n",
    "                            print(hamsters[i-1],count)\n",
    "                            continue\n",
    "                    elif hamsters[i-1]==\"H\": \n",
    "                        print(i,hamsters[i],\"第3种情况i-1在范围内是H\")\n",
    "                        if  not 0<=i+1<len(hamsters) or hamsters[i+1]==\"H\":\n",
    "                            return -1\n",
    "                        hamsters[i+1]=\"B\"\n",
    "                        count += 1\n",
    "                        print(hamsters[i+1],count)\n",
    "                else:\n",
    "                    print(i,hamsters[i],\"第4种情况i-1不在范围内\")\n",
    "                    if  not 0<=i+1<len(hamsters) or hamsters[i+1]==\"H\":\n",
    "                            return -1\n",
    "                    hamsters[i+1]=\"B\"\n",
    "                    count += 1\n",
    "                    print(hamsters[i+1],count)\n",
    "                \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        # hamsters = '.HH.HH.HH.HH..H'\n",
    "        if hamsters.count('HHH')!=0:\n",
    "            return -1\n",
    "        for i in range(len(hamsters)):\n",
    "            if hamsters[i] == 'H' and (i-1<0 or hamsters[i-1]=='H') and(i+1>=len(hamsters) or hamsters[i+1]=='H'):\n",
    "                return -1\n",
    "        b = [0 if (i==len(hamsters)-1 or hamsters[i+1]=='H')  else 1 for i in range(len(hamsters))]\n",
    "        s = [0 for _ in hamsters]\n",
    "        for i in range(len(hamsters)):\n",
    "            if i+1<len(hamsters) and hamsters[i]=='.' and hamsters[i+1]=='H' and b[i+1]==0:\n",
    "                s[i] = 1\n",
    "            if i-1>=0 and hamsters[i]=='.' and hamsters[i-1]=='H' and (i-2<0 or s[i-2]!=1):\n",
    "                s[i] = 1\n",
    "\n",
    "        return sum(s)\n",
    "             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        if 'H' not in hamsters: return 0\n",
    "        if '.' not in hamsters: return -1\n",
    "        if 'HHH' in hamsters or 'HH' == hamsters[:2] or 'HH' == hamsters[-2:]: return -1\n",
    "        def find_all(s,sub):\n",
    "            start = 0\n",
    "            pos = []\n",
    "            while True:\n",
    "                start = s.find(sub,start)\n",
    "                if start == -1: return pos\n",
    "                pos.append(start)\n",
    "                start += 1\n",
    "        def func(i,j):\n",
    "            # print(hamsters[i+1:j+1])\n",
    "            if hamsters[i+1] == '.':\n",
    "                i += 1\n",
    "            if hamsters[j] == '.':\n",
    "                j -= 1\n",
    "            return int(((j-i-1)/2+2)/2)\n",
    "        la = find_all(hamsters,'HH')\n",
    "        lb = find_all(hamsters,'..')\n",
    "        li = []\n",
    "        a,b = 0,0\n",
    "        while a<len(la) and b<len(lb):\n",
    "            if la[a]<lb[b]:\n",
    "                li.append(la[a])\n",
    "                a += 1\n",
    "            else:\n",
    "                li.append(lb[b])\n",
    "                b += 1\n",
    "        if a<len(la):\n",
    "            li += la[a:]\n",
    "        if b<len(lb):\n",
    "            li += lb[b:]\n",
    "        if not li: return func(-1,len(hamsters)-1)\n",
    "        if li[0] != 0: li = [-1]+li\n",
    "        li.append(len(hamsters)-1)\n",
    "        return sum([func(li[i],li[i+1]) for i in range(len(li)-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self,s):\n",
    "        if set(s)=={'.'}:\n",
    "            return 0\n",
    "\n",
    "        def checkFeasibility(j):\n",
    "            if j<0 or j>=len(s):\n",
    "                return 0\n",
    "            if s[j]=='H':\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        n=len(s)\n",
    "        # res=0\n",
    "        # i=0\n",
    "        # while i<n:\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         if (i+1<=n-1) and (s[i+1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=3\n",
    "        #         elif (i-1>=0) and (s[i-1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             i+=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        # tmpRes=0\n",
    "        # for i in range(n):\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         tmpRes+=1\n",
    "        # res=tmpRes\n",
    "        # i=0\n",
    "        # while i<=n:\n",
    "        #     if s[i:i+3]=='H.H':\n",
    "        #         res-=1\n",
    "        #         i+=3\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        BigM=100*n\n",
    "        dp=[0]*n\n",
    "        # dp(i)被定义为：对于下标i及以前而形成的子串的子问题\n",
    "        for i in range(n):\n",
    "            if s[i]=='H':\n",
    "                if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "                    return -1\n",
    "            if i>=1:\n",
    "                if s[i]=='H':\n",
    "                    if s[i-1]=='H':\n",
    "                        dp[i]=BigM   #locally impossible but globally possible\n",
    "                    else: # ...-H\n",
    "                        jump=2 #jump=2=len('-H')\n",
    "                        delta=1 #必用一个横杠(当考虑'-H'时，这里'-H'=s(i-1:i))\n",
    "                        dp[i]=dp[i-jump]+delta\n",
    "                        if i>=2:\n",
    "                            if s[i-2]=='H': #...H-H\n",
    "                                jump=3  #len('H-H')\n",
    "                                delta=1 #只需用一个横杠(当考虑'H-H'时，这里'H-H'=s(i-2:i))\n",
    "                                dp[i]=min(dp[i],dp[i-jump]+delta)\n",
    "                else: #s[i]='-'\n",
    "                    if s[i-1]=='H': #s(i-1,i)='H-'\n",
    "                        if i==1:###特殊处理开头情况\n",
    "                            dp[i]=1\n",
    "                        else:\n",
    "                            dp[i]=min(dp[i-2]+1,dp[i-1])   #min{用,不用}\n",
    "        #                                                     若用，则有jump=2=len('H-') & delta=1\n",
    "                    else: #s(i-1,i)='--'\n",
    "                        dp[i]=dp[i-1]    #此情况下用i处的(当下的)横杠毫无意义,所以直接复制上一轮的dp答案\n",
    "            if dp[i-1]>=BigM:###特殊处理(回头看下上一轮的dp迭代有没有出现impossible的情况，如果出现了现在impossible变成possible了---要更新值)\n",
    "                dp[i-1]=dp[i]\n",
    "        return dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self,s):\n",
    "        if set(s)=={'.'}:\n",
    "            return 0\n",
    "\n",
    "        def checkFeasibility(j):\n",
    "            if j<0 or j>=len(s):\n",
    "                return 0\n",
    "            if s[j]=='H':\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        n=len(s)\n",
    "        # res=0\n",
    "        # i=0\n",
    "        # while i<n:\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         if (i+1<=n-1) and (s[i+1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=3\n",
    "        #         elif (i-1>=0) and (s[i-1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             i+=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        # tmpRes=0\n",
    "        # for i in range(n):\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         tmpRes+=1\n",
    "        # res=tmpRes\n",
    "        # i=0\n",
    "        # while i<=n:\n",
    "        #     if s[i:i+3]=='H.H':\n",
    "        #         res-=1\n",
    "        #         i+=3\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        BigM=100*n\n",
    "        dp=[0]*n\n",
    "        # dp(i)被定义为：对于下标i及以前而形成的子串的子问题\n",
    "        for i in range(n):\n",
    "            if s[i]=='H':\n",
    "                if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "                    return -1\n",
    "            if i>=1:\n",
    "                if s[i]=='H':\n",
    "                    if s[i-1]=='H':\n",
    "                        dp[i]=BigM   #locally impossible but globally possible\n",
    "                    else: # ...-H\n",
    "                        jump=2 #jump=2=len('-H')\n",
    "                        delta=1 #必用一个横杠(当考虑'-H'时，这里'-H'=s(i-1:i))\n",
    "                        dp[i]=dp[i-jump]+delta\n",
    "                        if i>=2:\n",
    "                            if s[i-2]=='H': #...H-H\n",
    "                                jump=3  #len('H-H')\n",
    "                                delta=1 #只需用一个横杠(当考虑'H-H'时，这里'H-H'=s(i-2:i))\n",
    "                                dp[i]=min(dp[i],dp[i-jump]+delta)\n",
    "                else: #s[i]='-'\n",
    "                    if s[i-1]=='H': #s(i-1,i)='H-'\n",
    "                        if i==1:###特殊处理开头情况\n",
    "                            dp[i]=1\n",
    "                        else:\n",
    "                            dp[i]=min(dp[i-2]+1,dp[i-1])   #min{用,不用}\n",
    "        #                                                     若用，则有jump=2=len('H-') & delta=1\n",
    "                    else: #s(i-1,i)='--'\n",
    "                        dp[i]=dp[i-1]    #此情况下用i处的(当下的)横杠毫无意义,所以直接复制上一轮的dp答案\n",
    "            if dp[i-1]>=BigM:###特殊处理(回头看下上一轮的dp迭代有没有出现impossible的情况，如果出现了现在impossible变成possible了---要更新值)\n",
    "                dp[i-1]=dp[i]\n",
    "        return dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        if hamsters == 'H' or ('HHH' in hamsters) or hamsters[:2] == 'HH' or hamsters[-2:] == 'HH':\n",
    "            return -1\n",
    "        length = len(hamsters)\n",
    "        hamsters = list(hamsters)\n",
    "        for i in range(length-1):\n",
    "            if hamsters[i] == 'o':\n",
    "                continue\n",
    "            if hamsters[i] == 'H':\n",
    "                if hamsters[i+1] == '.' and (i == 0 or (i > 0 and hamsters[i-1] != 'o')):\n",
    "                    hamsters[i+1] = 'o'\n",
    "                elif hamsters[i+1] == 'H' and i > 0 and hamsters[i-1] == '.':\n",
    "                    hamsters[i-1] = 'o'\n",
    "            elif hamsters[i] == '.' and i == length-2 and hamsters[i+1] == 'H':\n",
    "                hamsters[i] = 'o'\n",
    "        print(hamsters)\n",
    "        return hamsters.count('o')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self,s):\n",
    "        if set(s)=={'.'}:\n",
    "            return 0\n",
    "\n",
    "        def checkFeasibility(j):\n",
    "            if j<0 or j>=len(s):\n",
    "                return 0\n",
    "            if s[j]=='H':\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        n=len(s)\n",
    "        # res=0\n",
    "        # i=0\n",
    "        # while i<n:\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         if (i+1<=n-1) and (s[i+1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=3\n",
    "        #         elif (i-1>=0) and (s[i-1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             i+=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        # tmpRes=0\n",
    "        # for i in range(n):\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         tmpRes+=1\n",
    "        # res=tmpRes\n",
    "        # i=0\n",
    "        # while i<=n:\n",
    "        #     if s[i:i+3]=='H.H':\n",
    "        #         res-=1\n",
    "        #         i+=3\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        BigM=100*n\n",
    "        dp=[0]*n\n",
    "        # dp(i)被定义为：对于下标i及以前而形成的子串的子问题\n",
    "        for i in range(n):\n",
    "            if s[i]=='H':\n",
    "                if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "                    return -1\n",
    "            if i>=1:\n",
    "                if s[i]=='H':\n",
    "                    if s[i-1]=='H':\n",
    "                        dp[i]=BigM #locally impossible but globally possible\n",
    "                    else: # ...-H\n",
    "                        jump=2 #jump=2=len('-H')\n",
    "                        delta=1 #必用一个横杠(当考虑'-H'时，这里'-H'=s(i-1:i))\n",
    "                        dp[i]=dp[i-jump]+delta\n",
    "                        if i>=2:\n",
    "                            if s[i-2]=='H': #...H-H\n",
    "                                jump=3  #len('H-H')\n",
    "                                delta=1 #只需用一个横杠(当考虑'H-H'时，这里'H-H'=s(i-2:i))\n",
    "                                dp[i]=min(dp[i],dp[i-jump]+delta)\n",
    "                else: #s[i]='-'\n",
    "                    if s[i-1]=='H': #s(i-1:i)='H-'\n",
    "                        if i==1:###特殊处理(开头情况)\n",
    "                            dp[i]=1\n",
    "                        else:\n",
    "                            dp[i]=min(dp[i-2]+1,dp[i-1])   #min{用,不用}\n",
    "        #                                                     若用，则有jump=2=len('H-') & delta=1\n",
    "                    else: #s(i-1:i)='--'\n",
    "                        dp[i]=dp[i-1]    #此情况下用i处的(当下的)横杠毫无意义,所以直接复制上一轮的dp答案\n",
    "            if dp[i-1]>=BigM:###特殊处理(回头看下上轮的dp计算是否出现了impossible的情况，如果出现了,现在impossible变成possible了,要更新值)\n",
    "                dp[i-1]=dp[i]\n",
    "        return dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self,s):\n",
    "        if set(s)=={'.'}:\n",
    "            return 0\n",
    "\n",
    "        def checkFeasibility(j):\n",
    "            if j<0 or j>=len(s):\n",
    "                return 0\n",
    "            if s[j]=='H':\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        n=len(s)\n",
    "        # res=0\n",
    "        # i=0\n",
    "        # while i<n:\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         if (i+1<=n-1) and (s[i+1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=3\n",
    "        #         elif (i-1>=0) and (s[i-1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             i+=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        # tmpRes=0\n",
    "        # for i in range(n):\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         tmpRes+=1\n",
    "        # res=tmpRes\n",
    "        # i=0\n",
    "        # while i<=n:\n",
    "        #     if s[i:i+3]=='H.H':\n",
    "        #         res-=1\n",
    "        #         i+=3\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        BigM=100*n\n",
    "        dp=[0]*n\n",
    "        # dp(i)被定义为：对于下标i及以前而形成的子串的子问题\n",
    "        for i in range(n):\n",
    "            if s[i]=='H':\n",
    "                if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "                    return -1\n",
    "            if i>=1:\n",
    "                if s[i]=='H':\n",
    "                    if s[i-1]=='H':\n",
    "                        dp[i]=BigM #locally impossible but globally possible\n",
    "                    else: # ...-H\n",
    "                        jump=2 #jump=2=len('-H')\n",
    "                        delta=1 #必用一个横杠(当考虑'-H'时，这里'-H'=s(i-1:i))\n",
    "                        dp[i]=dp[i-jump]+delta\n",
    "                        if i>=2:\n",
    "                            if s[i-2]=='H': #...H-H\n",
    "                                jump=3  #len('H-H')\n",
    "                                delta=1 #只需用一个横杠(当考虑'H-H'时，这里'H-H'=s(i-2:i))\n",
    "                                dp[i]=min(dp[i],dp[i-jump]+delta)\n",
    "                else: #s[i]='-'\n",
    "                    if s[i-1]=='H': #s(i-1:i)='H-'\n",
    "                        if i==1:###特殊处理(开头情况)\n",
    "                            dp[i]=1\n",
    "                        else:\n",
    "                            dp[i]=min(dp[i-2]+1,dp[i-1])   #min{用,不用}\n",
    "        #                                                     若用，则有jump=2=len('H-') & delta=1\n",
    "                    else: #s(i-1:i)='--'\n",
    "                        dp[i]=dp[i-1]    #此情况下用i处的(当下的)横杠毫无意义,所以直接复制上一轮的dp答案\n",
    "            if dp[i-1]>=BigM:###特殊处理(回头看下上轮的dp计算是否出现了impossible的情况，如果出现了,现在impossible变成possible了,要更新值)\n",
    "                dp[i-1]=dp[i]\n",
    "        return dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self,s):\n",
    "        if set(s)=={'.'}:\n",
    "            return 0\n",
    "\n",
    "        def checkFeasibility(j):\n",
    "            if j<0 or j>=len(s):\n",
    "                return 0\n",
    "            if s[j]=='H':\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        n=len(s)\n",
    "        # res=0\n",
    "        # i=0\n",
    "        # while i<n:\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         if (i+1<=n-1) and (s[i+1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=3\n",
    "        #         elif (i-1>=0) and (s[i-1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             i+=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        # tmpRes=0\n",
    "        # for i in range(n):\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         tmpRes+=1\n",
    "        # res=tmpRes\n",
    "        # i=0\n",
    "        # while i<=n:\n",
    "        #     if s[i:i+3]=='H.H':\n",
    "        #         res-=1\n",
    "        #         i+=3\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        BigM=100*n\n",
    "        dp=[0]*n\n",
    "        # dp(i)被定义为：对于下标i及以前而形成的子串的子问题\n",
    "        for i in range(n):\n",
    "            if s[i]=='H':\n",
    "                if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "                    return -1\n",
    "            if i>=1:\n",
    "                if s[i]=='H':\n",
    "                    if s[i-1]=='H':\n",
    "                        dp[i]=BigM #locally impossible but globally possible\n",
    "                    else: # ...-H\n",
    "                        jump=2 #jump=2=len('-H')\n",
    "                        delta=1 #必用一个横杠(当考虑'-H'时，这里'-H'=s(i-1:i))\n",
    "                        dp[i]=dp[i-jump]+delta\n",
    "                        if i>=2:\n",
    "                            if s[i-2]=='H': #...H-H\n",
    "                                jump=3  #len('H-H')\n",
    "                                delta=1 #只需用一个横杠(当考虑'H-H'时，这里'H-H'=s(i-2:i))\n",
    "                                dp[i]=min(dp[i],dp[i-jump]+delta)\n",
    "                else: #s[i]='-'\n",
    "                    if s[i-1]=='H': #s(i-1:i)='H-'\n",
    "                        if i==1:###特殊处理(开头情况)\n",
    "                            dp[i]=1\n",
    "                        else:\n",
    "                            dp[i]=min(dp[i-2]+1,dp[i-1])   #min{用,不用}\n",
    "        #                                                     若用，则有jump=2=len('H-') & delta=1\n",
    "                    else: #s(i-1:i)='--'\n",
    "                        dp[i]=dp[i-1]    #此情况下用i处的(当下的)横杠毫无意义,所以直接复制上一轮的dp答案\n",
    "            if dp[i-1]>=BigM:###特殊处理(回头看下上轮的dp计算是否出现了impossible的情况，如果出现了,现在impossible变成possible了,要更新值)\n",
    "                dp[i-1]=dp[i]\n",
    "        return dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self,s):\n",
    "        if set(s)=={'.'}:\n",
    "            return 0\n",
    "\n",
    "        def checkFeasibility(j):\n",
    "            if j<0 or j>=len(s):\n",
    "                return 0\n",
    "            if s[j]=='H':\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        n=len(s)\n",
    "        # res=0\n",
    "        # i=0\n",
    "        # while i<n:\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         if (i+1<=n-1) and (s[i+1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=3\n",
    "        #         elif (i-1>=0) and (s[i-1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             i+=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        # tmpRes=0\n",
    "        # for i in range(n):\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         tmpRes+=1\n",
    "        # res=tmpRes\n",
    "        # i=0\n",
    "        # while i<=n:\n",
    "        #     if s[i:i+3]=='H.H':\n",
    "        #         res-=1\n",
    "        #         i+=3\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        BigM=100*n\n",
    "        dp=[0]*n\n",
    "        for i in range(n):\n",
    "            if s[i]=='H':\n",
    "                if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "                    return -1\n",
    "            if i>=1:\n",
    "                if s[i]=='H':\n",
    "                    if s[i-1]=='H':\n",
    "                        dp[i]=BigM   #locally impossible but globally possible\n",
    "                    else: # ...-H\n",
    "                        jump=2 #jump=len('-H')\n",
    "                        delta=1 #必用一个横杠(当考虑'-H'时，这里'-H'=s(i-1:i))\n",
    "                        dp[i]=dp[i-jump]+delta\n",
    "                        if i>=2:\n",
    "                            if s[i-2]=='H': #...H-H\n",
    "                                jump=3  #len('H-H')\n",
    "                                delta=1 #只需用一个横杠(当考虑'H-H'时，这里'H-H'=s(i-2:i))\n",
    "                                dp[i]=min(dp[i],dp[i-jump]+delta)\n",
    "                else: #s[i]='-'\n",
    "                    if i-2>=0 and s[i-2]=='.':\n",
    "                        dp[i]=dp[i-1]\n",
    "                    else:\n",
    "                        dp[i]=min(dp[i-2]+1,dp[i-1]+0)   #min{Fill,NotFill}\n",
    "        #                                              if Fill (也即用s(i)处的这个横杠),则有jump=2=len('x-') where x='H' or '-'\n",
    "                    if (i==1) and (s[0]=='H'): #####特殊处理\n",
    "                        dp[i]=1\n",
    "            if dp[i-1]>=BigM: #####特殊处理\n",
    "                dp[i-1]=dp[i]\n",
    "        return dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self,s):\n",
    "        if set(s)=={'.'}:\n",
    "            return 0\n",
    "\n",
    "        def checkFeasibility(j):\n",
    "            if j<0 or j>=len(s):\n",
    "                return 0\n",
    "            if s[j]=='H':\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        n=len(s)\n",
    "        # res=0\n",
    "        # i=0\n",
    "        # while i<n:\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         if (i+1<=n-1) and (s[i+1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=3\n",
    "        #         elif (i-1>=0) and (s[i-1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             i+=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        # tmpRes=0\n",
    "        # for i in range(n):\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         tmpRes+=1\n",
    "        # res=tmpRes\n",
    "        # i=0\n",
    "        # while i<=n:\n",
    "        #     if s[i:i+3]=='H.H':\n",
    "        #         res-=1\n",
    "        #         i+=3\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        BigM=100*n\n",
    "        dp=[0]*n\n",
    "        # dp(i)被定义为：对于下标i及以前而形成的子串的子问题\n",
    "        for i in range(n):\n",
    "            if s[i]=='H':\n",
    "                if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "                    return -1\n",
    "            if i>=1:\n",
    "                if s[i]=='H':\n",
    "                    if s[i-1]=='H':\n",
    "                        dp[i]=BigM   #locally impossible but globally possible\n",
    "                    else: # ...-H\n",
    "                        jump=2 #jump=2=len('-H')\n",
    "                        delta=1 #必用一个横杠(当考虑'-H'时，这里'-H'=s(i-1:i))\n",
    "                        dp[i]=dp[i-jump]+delta\n",
    "                        if i>=2:\n",
    "                            if s[i-2]=='H': #...H-H\n",
    "                                jump=3  #len('H-H')\n",
    "                                delta=1 #只需用一个横杠(当考虑'H-H'时，这里'H-H'=s(i-2:i))\n",
    "                                dp[i]=min(dp[i],dp[i-jump]+delta)\n",
    "                else: #s[i]='-'\n",
    "                    if s[i-1]=='H': #s(i-1,i)='H-'\n",
    "                        if i==1:###特殊处理开头情况\n",
    "                            dp[i]=1\n",
    "                        else:\n",
    "                            dp[i]=min(dp[i-2]+1,dp[i-1])   #min{用,不用}\n",
    "        #                                                     若用，则有jump=2=len('H-') & delta=1\n",
    "                    else: #s(i-1,i)='--'\n",
    "                        dp[i]=dp[i-1]    #此情况下用i处的(当下的)横杠毫无意义\n",
    "            if dp[i-1]>=BigM: ###特殊处理(回头看下上一轮的dp迭代有没有出现impossible的情况，如果出现了现在impossible变成possible了---要更新值)\n",
    "                dp[i-1]=dp[i]\n",
    "        return dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self,s):\n",
    "        if set(s)=={'.'}:\n",
    "            return 0\n",
    "\n",
    "        def checkFeasibility(j):\n",
    "            if j<0 or j>=len(s):\n",
    "                return 0\n",
    "            if s[j]=='H':\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        n=len(s)\n",
    "        # res=0\n",
    "        # i=0\n",
    "        # while i<n:\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         if (i+1<=n-1) and (s[i+1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=3\n",
    "        #         elif (i-1>=0) and (s[i-1]=='.'):\n",
    "        #             res+=1\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             i+=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        # tmpRes=0\n",
    "        # for i in range(n):\n",
    "        #     if s[i]=='H':\n",
    "        #         if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "        #             return -1\n",
    "        #         tmpRes+=1\n",
    "        # res=tmpRes\n",
    "        # i=0\n",
    "        # while i<=n:\n",
    "        #     if s[i:i+3]=='H.H':\n",
    "        #         res-=1\n",
    "        #         i+=3\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return res\n",
    "###############################################################################################\n",
    "        BigM=100*n\n",
    "        dp=[0]*n\n",
    "        for i in range(n):\n",
    "            if s[i]=='H':\n",
    "                if checkFeasibility(i-1)==0 and checkFeasibility(i+1)==0:\n",
    "                    return -1\n",
    "            if i>=1:\n",
    "                if s[i]=='H':\n",
    "                    if s[i-1]=='H':\n",
    "                        dp[i]=BigM   #locally impossible but globally possible\n",
    "                    else: # ...-H\n",
    "                        jump=2 #jump=len('-H')\n",
    "                        delta=1 #必用一个横杠(当考虑'-H'时，这里'-H'=s(i-1:i))\n",
    "                        dp[i]=dp[i-jump]+delta\n",
    "                        if i>=2:\n",
    "                            if s[i-2]=='H': #...H-H\n",
    "                                jump=3  #len('H-H')\n",
    "                                delta=1 #只需用一个横杠(当考虑'H-H'时，这里'H-H'=s(i-2:i))\n",
    "                                dp[i]=min(dp[i],dp[i-jump]+delta)\n",
    "                else: #s[i]='-'\n",
    "                    if i-2>=0 and s[i-2]!='H':\n",
    "                        dp[i]=dp[i-1]\n",
    "                    else:\n",
    "                        dp[i]=min(dp[i-2]+1,dp[i-1]+0)   #min{Fill,NotFill}\n",
    "        #                                              if Fill (也即用s(i)处的这个横杠),则有jump=2=len('x-') where x='H' or '-'\n",
    "                    if (i==1) and (s[0]=='H'): #####特殊处理\n",
    "                        dp[i]=1\n",
    "            if dp[i-1]>=BigM: #####特殊处理\n",
    "                dp[i-1]=dp[i]\n",
    "        return dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        hamsters=list(hamsters)\n",
    "        ans=0\n",
    "        for i in range(1,len(hamsters)-1):\n",
    "            if hamsters[i-1]==\"H\" and hamsters[i]==\".\" and hamsters[i+1]==\"H\":\n",
    "                ans+=1\n",
    "                hamsters[i-1],hamsters[i],hamsters[i+1]=\"\",\"\",\"\"\n",
    "        hamsters=[\"+\"]+hamsters+[\"+\"]\n",
    "        for i in range(len(hamsters)):\n",
    "            if hamsters[i]==\"H\":\n",
    "                if hamsters[i-1]==\".\":\n",
    "                    hamsters[i-1]=\"+\"\n",
    "                    ans+=1\n",
    "                elif hamsters[i+1]==\".\":\n",
    "                    hamsters[i+1]=\"+\"\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, s: str) -> int:\n",
    "        hlist = list()\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            if s == \"H\":\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "        if n == 2:\n",
    "            if s == \"HH\":\n",
    "                return -1\n",
    "            elif s == \"..\":\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        if s[:2] == \"HH\" or s[-2:] == \"HH\":\n",
    "            return -1\n",
    "        \n",
    "        p = s.split(\".\")\n",
    "        for i in p:\n",
    "            if len(i) > 2:\n",
    "                return -1\n",
    "        \n",
    "            \n",
    "        for i in range(n):\n",
    "            if s[i] == \"H\":\n",
    "                hlist.append(i)\n",
    "        if len(hlist) == 1:\n",
    "            return 1\n",
    "        t = -1\n",
    "        ans = 0\n",
    "        for h in hlist:\n",
    "            if t == -1:\n",
    "                t = h\n",
    "            else:\n",
    "                if h - t == 2:\n",
    "                    ans += 1\n",
    "                    t = -1\n",
    "                elif h - t == 1:\n",
    "                    ans += 1\n",
    "                    t = h\n",
    "                elif h - t > 2:\n",
    "                    ans += 1\n",
    "                    t = h\n",
    "        if t != -1:\n",
    "            ans += 1\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBuckets(self, hamsters: str) -> int:\n",
    "        hamsters=list(hamsters)\n",
    "        ans=0\n",
    "        for i in range(1,len(hamsters)-1):\n",
    "            if hamsters[i-1]==\"H\" and hamsters[i]==\".\" and hamsters[i+1]==\"H\":\n",
    "                ans+=1\n",
    "                hamsters[i-1],hamsters[i],hamsters[i+1]=\"\",\"\",\"\"\n",
    "        hamsters=[\"+\"]+hamsters+[\"+\"]\n",
    "        for i in range(len(hamsters)):\n",
    "            if hamsters[i]==\"H\":\n",
    "                if hamsters[i-1]==\".\":\n",
    "                    hamsters[i-1]=\"+\"\n",
    "                    ans+=1\n",
    "                elif hamsters[i+1]==\".\":\n",
    "                    hamsters[i+1]=\"+\"\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    return -1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
